ДИНАМІЧНЕ РОЗПОДІЛ ПАМ'ЯТІ
Динамічний розподіл пам'яті надає програмісту великі можливості при зверненні до ресурсів пам'яті в процесі виконання програми, і коректна робота програми в істотному ступені залежить від правильного звернення до відповідних функцій.
Для виконання завдань по цій темі студенти повинні вміти працювати в покроковому відладчику, зображати схематичне розташування пам'яті при роботі з покажчиками.
Студенти повинні навчитися дослідженню програм, використовуючи режим відладки. Вони повинні переконатися в користі отладчика не тільки при пошуку помилок, але і на стадії розробки програми.
Для обов'язкового виконання рекомендуються завдання 1, 6, 7, 10. Завдання 4 можна використовувати в якості курсової роботи.
1. Моделі пам'яті
У BC + +2.0 існують кілька видів моделей пам'яті: tiny, small, medium, compact, large, huge. Програма може бути відкомпілювалися в будь-який з цих моделей, якщо встановити відповідний прапорець у Opions-Compiler-Code Generation-Model. При цьому використовуються різні набори вбудованих бібліотек і створюються різні obj-файли. Наприклад, для моделі large в директорії Lib є файли C0l.obj, Cl.lib, Mathl.lib та інші. Можлива помилка на етапі компонування ("Не можу знайти файл Сol.obj") викликана неповної версією пакета і невірним вибором моделі.
Моделі пам'яті не є частиною мови Сі, а залежать від використовуваної оболонки.
Коли програма завантажується в ОЗУ для виконання, їй відводиться певне місце, в якому можна виділити кілька областей: область коду (ОК); область даних, глобальних і статичних змінних (ОД); стек; купа (heap чи динамічна пам'ять).
Таблиця 1
Рис. 1
PSP являє собою префікс програмного сегменту, займає 256 байт і поміщається перед виконуваними файлами при їх завантаженні в пам'ять. Він містить змінні, використовувані MS-DOS для управління програмою, а також місце для перенесення даних оточення.
Область коду містить машинні коди функцій програми. Функції, приєднані до exe-файлу на стадії компонування, розміщуються поза області коду.
Область даних містить глобальні та статичні змінні, рядкові константи.
У стеці розміщуються локальні змінні, параметри, що передаються функціям, і ряд інших даних. Як правило, стек росте зверху вниз, займаючи пульсуючу безперервну область. У разі переповнення стека відбувається його "налезаніе" стека на область даних і видається відповідне повідомлення. Перевірка стека збільшує час роботи програми і її можна відключити в Options-Entry/Exit Code Generation-Stack options-Test stack overflow.
У купу дані розміщуються лише за вказівкою програміста і не мають імені. До них можна звернутися тільки за адресою, розташованому в локальної або глобальної змінної.
У деяких моделях пам'яті код може займати більше 64K. Області коду, даних і стек починаються з параграфів з номерами містяться, відповідно, в регістрах CS, DS, SS.
У режимі отладчика можна переглядати вміст регістрів у вікні Window-Register. При повторних запусках програми сегментні регістри можуть бути різні.
Значення сегментних регістрів, крім того, зберігаються в глобальних псевпеременних, що мають ту ж назву з підкресленням: _CS, _DS і т.д. Їх можна використовувати в програмі, наприклад, роздрукувати, враховуючи, що псевпеременние є шістнадцяткові беззнаковими числами printf ("CS =% x", _CS);
- Для змінної i, описаної як int i; i = 5; вікно перегляду має вигляд
-
Тут вказана адреса змінної в форматі [сегмент]: [зсув]. Повна адреса змінної дорівнює 8FAC0 + FFF4 = 9FAB4
- Для змінної ptri, описаної як
int i = 4, * ptri;
ptri = &i;
вікно перегляду має вигляд
Тут вказані: адреса самої змінної ptri, рівний 8FAC: FFF2; значення цієї змінної Ds: FFF4; а також вміст комірки за адресою Ds: FFF4, тобто значення i. Для того, щоб дізнатися вміст комірок, що оточують змінну i, потрібно скористатися комбінацією клавіш Alt-I, ввести початковий індекс (Starting index) і число комірок (Count). Якщо, наприклад, введені числа -5 і 15, то можна в наведеному вище вікні можна переглянути елементи масиву ptri [-5], ptri [-4], ..., ptri [10].
Об'єкти, розміщені в купі, не мають імені. Тому переглядати динамічні об'єкти можна тільки попереднім способом, тобто за адресою.
Область даних займає частину ОЗУ, що містить параграфи з номерами від DS SS-1. Таким чином, розмір області даних дорівнює (SS-DS) * 0x10.
Стек починається з параграфа SS, але зростає справа наліво, від старших адрес до молодших. Нові дані містяться в стек у вершині стека. Зсув вершини стека щодо SS одно SP. Таким чином, повна адреса вершини дорівнює SS: SP. На початку програми стек порожній, тому він займає осередку з адресами від SS * 0x10 до SS * 0x10, а розмір стека дорівнює SP.
На купу залишається пам'ять з адреси SS * 0x10 + SP по 0xA0000 = 640K.
Реальний розмір купи залежить від способу запуску програми. Сама оболонка Borland C + +2.0 займає в ОЗУ порядку 200K, і для програми, виполнямой з оболонки, залишається небагато місця - приблизно 300K. Якщо ж програма запускається з командного рядка DOS чи з Norton Commander, то купа буде значно більше.
При виконанні програми з оболонки і в відладчик під купу відводиться ще менше місця, тому її розмір у цьому випадку дозволяється встановлювати вручну за допомогою опції Options-Debugger-Program heap size.
2. Основні функції ДРП
Виділяє блок ДП розміром size байт. Тут size_t збігається з типом unsigned int. Таким чином, блок не перевершує розмір в 64K. У разі відсутності безперервного блоку замовленої довжини, повертається NULL.
Приклад 1. Виділення масиву для 1000 чисел типу float.
main () {
float * ptrf;
if ((ptrf = (float *) malloc (1000 * sizeof (float)) == NULL)
printf ("\ nОшібка при виділенні пам'яті!");
}
Звільняє блок ДП, що починається з адреси block. Ця адреса повинен знаходиться в заголовку раніше виділеного блоку (див. п.3). В іншому випадку, буде звільнений випадковий блок і виникне логічна помилка. Динамічні змінні не звільняються автоматично при виході з області дії і, таким чином, засмічують купу.
Змінює розмір блоку, на який вказує block. Новий розмір блоку буде дорівнює size. Стара інформація зберігається. При нестачі вільних байт блок буде переміщений у нове місце з одночасним копіюванням інформації. Функція повертає адресу нового блоку, не змінюючи змінну block.
Приклад 2. Виділення пам'яті під двовимірний масив
main () {
float ** A;
int n = 5, n = 10;
A = (float **) malloc (m * sizeof (float *));
if (A == NULL)
{
printf ("\ nОшібка при виділенні пам'яті під масив покажчиків!");
exit (1);
}
for (int i = 0; i <m; i + +)
{
A [i] = (float *) malloc (n * sizeof (float));
if (A [i] == NULL)
{
printf ("\ nОшібка пам'яті під% d-й рядок!", i);
for (int j = 0; j <i; j + +)
free (A [j]);
free (A);
exit (2);
}
/ / ... ....
for (i = 0; i <m; i + +)
free (A [i]);
free (A);
}
3. Менеджер ДРП
Управлінням ДП займається спеціальний фрагмент коду, що викликається у функціях ДРП. Він називається менеджером ДП. Ми досліджуємо роботу менеджера в моделі пам'яті large. В інших моделях менеджер влаштований по-іншому.
Спочатку менеджер розглядає купу як вільну область. При кожному зверненні до пам'яті виділяється безперервний блок, що складається з одного або декількох параграфів. У першому параграфі є заголовок блоку. При звільненні пам'яті блок позначається як вільний. Таким чином, в процесі роботи програми вільні і зайняті блоки починають чергуватися. В результаті збільшується фрагментація купи, коли загальною вільної пам'яті багато, а безперервного блоку необхідної довжини немає.
Виділяється блок пам'яті має вигляд
У заголовку знаходяться:
¾ довжина блоку в параграфах (2 байти),
¾ сегментний адресу попереднього блоку (2 байти),
¾ далі йдуть дані. Адреса початку даних і повертається функціями ДРП.
Блоки організовані в однозв''язних список. При запуску програми на початку купі виділяється блок для системних потреб. Перший виділений програмою блок буде посилатися на наявний блок і т.д. При звільненні блоку в його заголовку обнуляється посилання на попередній блок. Довжина блоку не змінюється, а в інформаційну область заносяться дані, використовувані при коригуванні купи.
Таким чином, знаючи адресу останнього зайнятого блоку, можна визначити довжину, адресу і статус інших блоків. Розглянемо програму
main () {
char * block1 = (char *) malloc (100);
char * block2 = (char *) malloc (110);
char * block3 = (char *) malloc (120);
free (block2);
}
Виконуючи її в відладчик, побачимо, що до звільнення другого блоку купа буде мати вигляд (конкретні адреси будуть іншими!)
Рис. 2
Після виконання оператора free (block2) купа буде мати вигляд
Рис. 3
Зауваження 1. Особливість динамічних символьних рядків.
Розглянемо фрагмент коду, створює динамічну рядок.
main ()
{
char * str; / / осередок str знаходиться в стеку
str = (char *) malloc (13);
strcpy (str, "Hello, World!");
/ / Рядок Hello, World! поміщається в купу
}
Рядок "Hello, World!" реально складається з 13 символів, тому що крім самих символів містить 0 - ознака кінця рядка. Тому, якщо виділити тільки 12 елементів
Str = (char *) malloc (12),
то ознака кінця рядка "залізе" на заголовок наступного блоку ДП і змінить довжину цього блоку. Якби довжина рядка була менше 12 байт, то фраза вмістилася б у першому параграфі, і помилки не сталося б. Джерело добре прихованої логічної помилки!
4. Додаткові фунції ДРП
Повертає розмір невикористаної пам'яті в байтах, розташованої за останнім зайнятим блоком. "Дірки" в купі не враховуються.
Виділяє та обнуляє пам'ять для Nitems фрагментів по SizeOfItem байт кожен. Розмір фрагмента не перевершує 64K, але загальний об'єм пам'яті може перевищувати 64K. У разі невдачі повертається NULL.
Переглядає купу і перевіряє для кожного блоку покажчики, розмір та іншу критичну інформацію. Якщо все нормально, то повертається значення більше 0. В іншому випадку, повертається негативне число.
Переглядає купу блок за блоком. Передбачається, що збоїв в купі немає, для цього використовуйте heapcheck. Фнукція отримує покажчик на структуру heapinfo. При першому виклику, встановіть hi.ptr в 0. Функція встановлює цей покажчик на адресу чергового блоку. Інші поля структури size, in_use дозволяють визначити розмір блоку в байтах і його зайнятість. Для чергового блоку функція поверне _HEAPOK, для останнього блоку _HEAPEND.
Приклад 3. Зайняті і вільні блоки.
# Include <stdio.h>
# Include <alloc.h>
# Define NUM_PTRS 4
# Define NUM_BYTES 20
int main (void)
{
struct heapinfo hi;
char * array [NUM_PTRS];
for (int i = 0; i <NUM_PTRS; i + +)
array [i] = (char *) malloc (NUM_BYTES);
for (i = 0; i <NUM_PTRS; i + = 2)
free (array [i]);
hi.ptr = NULL;
printf ("Розмір Статус \ n");
printf ("---- ------ \ n");
while (heapwalk (& hi) == _HEAPOK)
{
printf ("% 7u", hi.size);
printf ("% s \ n", (hi.in_use? "використовується": "вільний"));
}
return 0;
}
У результаті буде надруковано
Заповнює байти вільних блоків купи константним значенням fillvalue.
Перевіряє байти вільних блоків купи на їх рівність константними значенням fillvalue.
5. Лабораторні завдання
Області пам'яті
Для наступної програми вкажіть значення сегментних регістрів. Вкажіть абсолютні адреси і розміри в байтах області коду; області даних, глобальних і статичних змінних; стека; купи. Модель пам'яті large. Визначте в відладчик адреси і розміщення по областях змінних: main; Privet; Dlit у функції main; i і Dlit у функції Privet; printf.
void Privet (int sound); / / прототип функції Privet
main () {
int Dlit = 5;
Privet (Dlit); / / виклик функції Privet
}
void Privet (int Dlit) {/ / заголовок функції Privet
{
printf ("Привіт! \ n");
printf ("З добрим ранком!");
for (int i = 0; i <Dlit; i + +) / / друкує перші Dlit
printf ("% c", i); / / символів ascii-таблиці
}
Дослідження менеджера ДРП
Виділіть динамічну пам'ять для трьох даних типу char. Адреси збережіть в змінних char * x, * y, * z. Визначте в відладчик адреси * x, * y, * z. Переконайтеся, що для кажго з однобайтових даних буде відведено в купі 16 байт, тобто цілий параграф.
Однозв''язних список менеджера
Додайте в купі кілька даних різного типу, знайдіть їх адреси, розмір блоків. Переконайтеся в наявності односвязного списку.
Новий менеджер
Мова Сі не пускає дефрагментації ДП. Напишіть свій менеджер, який містить функції mymalloc, myfree, mydefrag.
Сума вільних блоків
Визначте сумарний обсяг "дірок" в купі, що утворилися після звільнення блоків.
Виділення пам'яті під одновимірний масив
Виділіть пам'ять під 20 змінних типу int. Заповніть їх випадковими цілими числами з інтервалу від -3 7. Виведіть їх на екран.
Виділення пам'яті під двовимірний масив
Виділіть пам'ять під двовимірний масив 3х5 типу float. Заповніть їх випадковими числами з інтервалу від -3.6 7.4 з кроком 0.1. Виведіть їх на екран у вигляді таблиці. Масив подайте у вигляді рядка.
Структура для матриці змінних розмірностей.
Створіть структуру для зберігання інформації про матрицю змінних розмірностей. Розгляньте дві можливості
Struct Matr1 {int m, n; int * ptr;};
Struct Matr2 {int m, n; int ** ptr;};
Напишіть функції
int DinMatr1 (Matr1 * matr);
int DinMatr2 (Matr2 * matr);
для коректного виділення пам'яті під масив
Множення матриць
Напишіть функцію множення матриць змінних розмірностей.
Введення чисел
З клавіатури вводяться натуральні числа. Ознака кінця введення - число 0. Зберігайте числа в купі. Після закінчення введення видайте числа на екран.
Список рядків
Створіть однозв''язних список для зберігання текстових рядків, що вводяться з клавіатури. Виведіть їх на екран у зворотному порядку.
Норма матриці
Октаедричній нормою квадратної матриці А, nxn, називається число ÷ ÷ A ÷ ÷ ∞ = max {÷ a 1 j ÷ + ÷ a 2 j ÷ + ... + ÷ a nj ÷: j = 1, ... n}. Напишіть функцію для обчислення норми матриці. Розміри матриці довільний.
Найбільша за розміром квадратна матриця.
Знайдіть найбільший розмір N, для якого в купі можна виділити в пам'яті місце для квадратної матриці NxN чисел типу float. Отримайте результат при запуску програми з командного рядка DOS і з оболонки BC.
Модифікація функції coreleft.
Напишіть функцію обчислення загального розміру вільної купи.
Чи вільна купа?
Напишіть функцію визначальну, чи вільна купа.
Робота з файлом.
Запишіть динамічну матрицю в файл, прочитайте з файлу і роздрукуйте.
2. Керніган Б, Рітчі Д. Мова програмування Сі. Завдання за курсом Сі. М.: фін. стат., 1985.
3. Уінер Р. Мова ТурбоСі. М.: Світ, 1991.
4. Хинт К. Сі без проблем. Керівництво користувача. М.: Біном, 1997.
Трофімов С.П. Програмування в Сі. Організація введення-виведення / / Метод. вказівки, Єкатеринбург, Вид-во УГТУ, 1998, 20 с.
Введення
Метою даної роботи є вироблення навичок використання динамічної пам'яті, привчання до усвідомленого вибору відповідної моделі пам'яті при компіляції програми.Динамічний розподіл пам'яті надає програмісту великі можливості при зверненні до ресурсів пам'яті в процесі виконання програми, і коректна робота програми в істотному ступені залежить від правильного звернення до відповідних функцій.
Для виконання завдань по цій темі студенти повинні вміти працювати в покроковому відладчику, зображати схематичне розташування пам'яті при роботі з покажчиками.
Студенти повинні навчитися дослідженню програм, використовуючи режим відладки. Вони повинні переконатися в користі отладчика не тільки при пошуку помилок, але і на стадії розробки програми.
Для обов'язкового виконання рекомендуються завдання 1, 6, 7, 10. Завдання 4 можна використовувати в якості курсової роботи.
1. Моделі пам'яті
Види моделей
Моделлю пам'яті називається набір опцій компілятора, що визначає розмір і структуру оперативної пам'яті, що надається програмі при її виконанні.У BC + +2.0 існують кілька видів моделей пам'яті: tiny, small, medium, compact, large, huge. Програма може бути відкомпілювалися в будь-який з цих моделей, якщо встановити відповідний прапорець у Opions-Compiler-Code Generation-Model. При цьому використовуються різні набори вбудованих бібліотек і створюються різні obj-файли. Наприклад, для моделі large в директорії Lib є файли C0l.obj, Cl.lib, Mathl.lib та інші. Можлива помилка на етапі компонування ("Не можу знайти файл Сol.obj") викликана неповної версією пакета і невірним вибором моделі.
Моделі пам'яті не є частиною мови Сі, а залежать від використовуваної оболонки.
Коли програма завантажується в ОЗУ для виконання, їй відводиться певне місце, в якому можна виділити кілька областей: область коду (ОК); область даних, глобальних і статичних змінних (ОД); стек; купа (heap чи динамічна пам'ять).
Таблиця 1
| вид моделі пам'яті | максимальний розмір | ||||
| Область коду | область даних | стек | купа | взаємне розташування | |
| tiny | 64К | 64К | 64К | 64К | всі області в одному сегменті |
| small | 64К | 64К | 64К | 64К | ОД, стік і купа в одному сегменті |
| medium | 1М | 64К | 64К | 64К | різні сегменти |
| compact | 1М | 64К | 64К | 1М | різні сегменти |
| large | 1М | 64К | 64К | 1М | різні сегменти |
| huge | 1М | 64К | 64К | 1М | різні сегменти |
Модель Large
Моделі пам'яті влаштовані по-різному. Розглянемо розташування областей пам'яті в моделі large. PSP код дані стек купа 640K |
Рис. 1
PSP являє собою префікс програмного сегменту, займає 256 байт і поміщається перед виконуваними файлами при їх завантаженні в пам'ять. Він містить змінні, використовувані MS-DOS для управління програмою, а також місце для перенесення даних оточення.
Область коду містить машинні коди функцій програми. Функції, приєднані до exe-файлу на стадії компонування, розміщуються поза області коду.
Область даних містить глобальні та статичні змінні, рядкові константи.
У стеці розміщуються локальні змінні, параметри, що передаються функціям, і ряд інших даних. Як правило, стек росте зверху вниз, займаючи пульсуючу безперервну область. У разі переповнення стека відбувається його "налезаніе" стека на область даних і видається відповідне повідомлення. Перевірка стека збільшує час роботи програми і її можна відключити в Options-Entry/Exit Code Generation-Stack options-Test stack overflow.
У купу дані розміщуються лише за вказівкою програміста і не мають імені. До них можна звернутися тільки за адресою, розташованому в локальної або глобальної змінної.
Сегментні регістри
Сегмент - це область пам'яті розміром не більше 64K, створена для зберігання коду, даних або стека. Сегменти завжди вирівняні на кордон параграфа (16 байт), тому їх адресу виходить множенням сегментного регістра на 0x10 = 16.У деяких моделях пам'яті код може займати більше 64K. Області коду, даних і стек починаються з параграфів з номерами містяться, відповідно, в регістрах CS, DS, SS.
У режимі отладчика можна переглядати вміст регістрів у вікні Window-Register. При повторних запусках програми сегментні регістри можуть бути різні.
Значення сегментних регістрів, крім того, зберігаються в глобальних псевпеременних, що мають ту ж назву з підкресленням: _CS, _DS і т.д. Їх можна використовувати в програмі, наприклад, роздрукувати, враховуючи, що псевпеременние є шістнадцяткові беззнаковими числами printf ("CS =% x", _CS);
Перегляд змінних
У режимі отладчика можна визначити адреси і значення змінних, що знаходяться в своїй області видимості, з допомогою Alt-F4. Наприклад.- Для змінної i, описаної як int i; i = 5; вікно перегляду має вигляд
-
| 8FAC: FFF4 | 5 (0x0005) |
| Int | |
- Для змінної ptri, описаної як
int i = 4, * ptri;
ptri = &i;
вікно перегляду має вигляд
| 8FAC: FFF2 | п | Ds: FFF4 |
| [0] | 4 (0x0004) | |
| Int * | ||
Об'єкти, розміщені в купі, не мають імені. Тому переглядати динамічні об'єкти можна тільки попереднім способом, тобто за адресою.
Абсолютні адреси і розміри областей пам'яті в моделі large
Область коду займає частину ОЗУ, що містить параграфи з номерами від CS до DS-1. Таким чином, розмір області коду дорівнює (DS-CS) * 0x10.Область даних займає частину ОЗУ, що містить параграфи з номерами від DS SS-1. Таким чином, розмір області даних дорівнює (SS-DS) * 0x10.
Стек починається з параграфа SS, але зростає справа наліво, від старших адрес до молодших. Нові дані містяться в стек у вершині стека. Зсув вершини стека щодо SS одно SP. Таким чином, повна адреса вершини дорівнює SS: SP. На початку програми стек порожній, тому він займає осередку з адресами від SS * 0x10 до SS * 0x10, а розмір стека дорівнює SP.
На купу залишається пам'ять з адреси SS * 0x10 + SP по 0xA0000 = 640K.
Реальний розмір купи залежить від способу запуску програми. Сама оболонка Borland C + +2.0 займає в ОЗУ порядку 200K, і для програми, виполнямой з оболонки, залишається небагато місця - приблизно 300K. Якщо ж програма запускається з командного рядка DOS чи з Norton Commander, то купа буде значно більше.
При виконанні програми з оболонки і в відладчик під купу відводиться ще менше місця, тому її розмір у цьому випадку дозволяється встановлювати вручну за допомогою опції Options-Debugger-Program heap size.
2. Основні функції ДРП
Виділення пам'яті
void * malloc (size_t size);Виділяє блок ДП розміром size байт. Тут size_t збігається з типом unsigned int. Таким чином, блок не перевершує розмір в 64K. У разі відсутності безперервного блоку замовленої довжини, повертається NULL.
Приклад 1. Виділення масиву для 1000 чисел типу float.
main () {
float * ptrf;
if ((ptrf = (float *) malloc (1000 * sizeof (float)) == NULL)
printf ("\ nОшібка при виділенні пам'яті!");
}
Звільнення пам'яті
void free (void * block);Звільняє блок ДП, що починається з адреси block. Ця адреса повинен знаходиться в заголовку раніше виділеного блоку (див. п.3). В іншому випадку, буде звільнений випадковий блок і виникне логічна помилка. Динамічні змінні не звільняються автоматично при виході з області дії і, таким чином, засмічують купу.
Перевиделеніе пам'яті
void * realloc (void * block, size_t size);Змінює розмір блоку, на який вказує block. Новий розмір блоку буде дорівнює size. Стара інформація зберігається. При нестачі вільних байт блок буде переміщений у нове місце з одночасним копіюванням інформації. Функція повертає адресу нового блоку, не змінюючи змінну block.
Приклад 2. Виділення пам'яті під двовимірний масив
main () {
float ** A;
int n = 5, n = 10;
A = (float **) malloc (m * sizeof (float *));
if (A == NULL)
{
printf ("\ nОшібка при виділенні пам'яті під масив покажчиків!");
exit (1);
}
for (int i = 0; i <m; i + +)
{
A [i] = (float *) malloc (n * sizeof (float));
if (A [i] == NULL)
{
printf ("\ nОшібка пам'яті під% d-й рядок!", i);
for (int j = 0; j <i; j + +)
free (A [j]);
free (A);
exit (2);
}
/ / ... ....
for (i = 0; i <m; i + +)
free (A [i]);
free (A);
}
3. Менеджер ДРП
Управлінням ДП займається спеціальний фрагмент коду, що викликається у функціях ДРП. Він називається менеджером ДП. Ми досліджуємо роботу менеджера в моделі пам'яті large. В інших моделях менеджер влаштований по-іншому.
Спочатку менеджер розглядає купу як вільну область. При кожному зверненні до пам'яті виділяється безперервний блок, що складається з одного або декількох параграфів. У першому параграфі є заголовок блоку. При звільненні пам'яті блок позначається як вільний. Таким чином, в процесі роботи програми вільні і зайняті блоки починають чергуватися. В результаті збільшується фрагментація купи, коли загальною вільної пам'яті багато, а безперервного блоку необхідної довжини немає.
Виділяється блок пам'яті має вигляд
| 2 | 2 | 14 | 16 | ... .. | 16 |
У заголовку знаходяться:
¾ довжина блоку в параграфах (2 байти),
¾ сегментний адресу попереднього блоку (2 байти),
¾ далі йдуть дані. Адреса початку даних і повертається функціями ДРП.
Блоки організовані в однозв''язних список. При запуску програми на початку купі виділяється блок для системних потреб. Перший виділений програмою блок буде посилатися на наявний блок і т.д. При звільненні блоку в його заголовку обнуляється посилання на попередній блок. Довжина блоку не змінюється, а в інформаційну область заносяться дані, використовувані при коригуванні купи.
Таким чином, знаючи адресу останнього зайнятого блоку, можна визначити довжину, адресу і статус інших блоків. Розглянемо програму
main () {
char * block1 = (char *) malloc (100);
char * block2 = (char *) malloc (110);
char * block3 = (char *) malloc (120);
free (block2);
}
Виконуючи її в відладчик, побачимо, що до звільнення другого блоку купа буде мати вигляд (конкретні адреси будуть іншими!)
| 0х90EF | ... | 0x0008 | 0x910F | .... | 0x0008 | 0x9116 |
| Block1 | Block2 | Block3 |
Після виконання оператора free (block2) купа буде мати вигляд
| 0х90EF | ... | 0x0008 | 0x0000 | .... | 0x0008 | 0x9116 |
| Block1 | Block2 | Block3 |
Зауваження 1. Особливість динамічних символьних рядків.
Розглянемо фрагмент коду, створює динамічну рядок.
main ()
{
char * str; / / осередок str знаходиться в стеку
str = (char *) malloc (13);
strcpy (str, "Hello, World!");
/ / Рядок Hello, World! поміщається в купу
}
Рядок "Hello, World!" реально складається з 13 символів, тому що крім самих символів містить 0 - ознака кінця рядка. Тому, якщо виділити тільки 12 елементів
Str = (char *) malloc (12),
то ознака кінця рядка "залізе" на заголовок наступного блоку ДП і змінить довжину цього блоку. Якби довжина рядка була менше 12 байт, то фраза вмістилася б у першому параграфі, і помилки не сталося б. Джерело добре прихованої логічної помилки!
4. Додаткові фунції ДРП
Визначення розміру вільної області купи
unsigned long coreleft (void);Повертає розмір невикористаної пам'яті в байтах, розташованої за останнім зайнятим блоком. "Дірки" в купі не враховуються.
Блокове виділення пам'яті
void * calloc (size_t NItems, size_t SizeOfItem);Виділяє та обнуляє пам'ять для Nitems фрагментів по SizeOfItem байт кожен. Розмір фрагмента не перевершує 64K, але загальний об'єм пам'яті може перевищувати 64K. У разі невдачі повертається NULL.
Перевірка цілісності купи
int heapcheck (void);Переглядає купу і перевіряє для кожного блоку покажчики, розмір та іншу критичну інформацію. Якщо все нормально, то повертається значення більше 0. В іншому випадку, повертається негативне число.
Перегляд блоків купи
int heapwalk (struct heapinfo * hi);Переглядає купу блок за блоком. Передбачається, що збоїв в купі немає, для цього використовуйте heapcheck. Фнукція отримує покажчик на структуру heapinfo. При першому виклику, встановіть hi.ptr в 0. Функція встановлює цей покажчик на адресу чергового блоку. Інші поля структури size, in_use дозволяють визначити розмір блоку в байтах і його зайнятість. Для чергового блоку функція поверне _HEAPOK, для останнього блоку _HEAPEND.
Приклад 3. Зайняті і вільні блоки.
# Include <stdio.h>
# Include <alloc.h>
# Define NUM_PTRS 4
# Define NUM_BYTES 20
int main (void)
{
struct heapinfo hi;
char * array [NUM_PTRS];
for (int i = 0; i <NUM_PTRS; i + +)
array [i] = (char *) malloc (NUM_BYTES);
for (i = 0; i <NUM_PTRS; i + = 2)
free (array [i]);
hi.ptr = NULL;
printf ("Розмір Статус \ n");
printf ("---- ------ \ n");
while (heapwalk (& hi) == _HEAPOK)
{
printf ("% 7u", hi.size);
printf ("% s \ n", (hi.in_use? "використовується": "вільний"));
}
return 0;
}
У результаті буде надруковано
| Розмір | Статус |
| 528 | Використовується |
| 32 | Вільний |
| 32 | Використовується |
| 32 | Вільний |
| 32 | Використовується |
Ініціалізація вільних блоків купи
int heapfillfree (unsigned int fillvalue);Заповнює байти вільних блоків купи константним значенням fillvalue.
Перевірка вільних блоків купи
int heapcheckfree (unsigned int fillvalue);Перевіряє байти вільних блоків купи на їх рівність константними значенням fillvalue.
Функції групи far.
У моделях пам'яті, де купа не перевищує 64K, можна використовувати пам'ять поза цією областю - дальню купу. Для роботи з далекої купою є свої версії функцій, c префіксом far.5. Лабораторні завдання
Області пам'яті
Для наступної програми вкажіть значення сегментних регістрів. Вкажіть абсолютні адреси і розміри в байтах області коду; області даних, глобальних і статичних змінних; стека; купи. Модель пам'яті large. Визначте в відладчик адреси і розміщення по областях змінних: main; Privet; Dlit у функції main; i і Dlit у функції Privet; printf.
void Privet (int sound); / / прототип функції Privet
main () {
int Dlit = 5;
Privet (Dlit); / / виклик функції Privet
}
void Privet (int Dlit) {/ / заголовок функції Privet
{
printf ("Привіт! \ n");
printf ("З добрим ранком!");
for (int i = 0; i <Dlit; i + +) / / друкує перші Dlit
printf ("% c", i); / / символів ascii-таблиці
}
Дослідження менеджера ДРП
Виділіть динамічну пам'ять для трьох даних типу char. Адреси збережіть в змінних char * x, * y, * z. Визначте в відладчик адреси * x, * y, * z. Переконайтеся, що для кажго з однобайтових даних буде відведено в купі 16 байт, тобто цілий параграф.
Однозв''язних список менеджера
Додайте в купі кілька даних різного типу, знайдіть їх адреси, розмір блоків. Переконайтеся в наявності односвязного списку.
Новий менеджер
Мова Сі не пускає дефрагментації ДП. Напишіть свій менеджер, який містить функції mymalloc, myfree, mydefrag.
Сума вільних блоків
Визначте сумарний обсяг "дірок" в купі, що утворилися після звільнення блоків.
Виділення пам'яті під одновимірний масив
Виділіть пам'ять під 20 змінних типу int. Заповніть їх випадковими цілими числами з інтервалу від -3 7. Виведіть їх на екран.
Виділення пам'яті під двовимірний масив
Виділіть пам'ять під двовимірний масив 3х5 типу float. Заповніть їх випадковими числами з інтервалу від -3.6 7.4 з кроком 0.1. Виведіть їх на екран у вигляді таблиці. Масив подайте у вигляді рядка.
Структура для матриці змінних розмірностей.
Створіть структуру для зберігання інформації про матрицю змінних розмірностей. Розгляньте дві можливості
Struct Matr1 {int m, n; int * ptr;};
Struct Matr2 {int m, n; int ** ptr;};
Напишіть функції
int DinMatr1 (Matr1 * matr);
int DinMatr2 (Matr2 * matr);
для коректного виділення пам'яті під масив
Множення матриць
Напишіть функцію множення матриць змінних розмірностей.
Введення чисел
З клавіатури вводяться натуральні числа. Ознака кінця введення - число 0. Зберігайте числа в купі. Після закінчення введення видайте числа на екран.
Список рядків
Створіть однозв''язних список для зберігання текстових рядків, що вводяться з клавіатури. Виведіть їх на екран у зворотному порядку.
Норма матриці
Октаедричній нормою квадратної матриці А, nxn, називається число ÷ ÷ A ÷ ÷ ∞ = max {÷ a 1 j ÷ + ÷ a 2 j ÷ + ... + ÷ a nj ÷: j = 1, ... n}. Напишіть функцію для обчислення норми матриці. Розміри матриці довільний.
Найбільша за розміром квадратна матриця.
Знайдіть найбільший розмір N, для якого в купі можна виділити в пам'яті місце для квадратної матриці NxN чисел типу float. Отримайте результат при запуску програми з командного рядка DOS і з оболонки BC.
Модифікація функції coreleft.
Напишіть функцію обчислення загального розміру вільної купи.
Чи вільна купа?
Напишіть функцію визначальну, чи вільна купа.
Робота з файлом.
Запишіть динамічну матрицю в файл, прочитайте з файлу і роздрукуйте.
Бібліографічний список
1. Керніган Б, Рітчі Д. Мова програмування Сі. М.: Фін. і стат., 1992.2. Керніган Б, Рітчі Д. Мова програмування Сі. Завдання за курсом Сі. М.: фін. стат., 1985.
3. Уінер Р. Мова ТурбоСі. М.: Світ, 1991.
4. Хинт К. Сі без проблем. Керівництво користувача. М.: Біном, 1997.
Трофімов С.П. Програмування в Сі. Організація введення-виведення / / Метод. вказівки, Єкатеринбург, Вид-во УГТУ, 1998, 20 с.